#include <stdio.h>
#include <stdlib.h>

#define SIZE 9
#define SQRTS 3

void initializeBoard(int board[SIZE][SIZE]){
	int i,j;
	for(i=0;i<SIZE;i++){
		for(j=0;j<SIZE;j++){
			board[i][j]=0;
		}
	}
}
int boardIsFull(int board[SIZE][SIZE]){
	int i,j;
	for(i=0;i<SIZE;i++){
		for(j=0;j<SIZE;j++){
			if(board[i][j]==0) return 0;
		}
	}
	return 1;
}
void initializeAuxilaryArray(int auxilaryArray[SIZE]){
	int i;
	for(i=0;i<=SIZE;i++) auxilaryArray[i]=0;
}
int auxilaryArrayIsFull(int auxilaryArray[SIZE]){
	int i,sum=0;
	for(i=0;i<=SIZE;i++){
		sum+=auxilaryArray[i];
	}
	if(sum==9) return 1;
	return 0;
}
int cubeIsCorrect(int board[SIZE][SIZE], int x, int y){

	int auxilaryArray[SIZE];
	initializeAuxilaryArray(auxilaryArray);

	int i,j,t;

	for(i=x;i<x+SQRTS;i++){
		for(j=y;j<y+SQRTS;j++){
			t=board[i][j];
			auxilaryArray[t]=1;
		}
	}


	if(auxilaryArrayIsFull(auxilaryArray)) return 1;
	return 0;
}
int rowIsCorrect(int board[SIZE][SIZE], int row){
	int auxilaryArray[SIZE];
	initializeAuxilaryArray(auxilaryArray);
	int i,t;

	for(i=0;i<=SIZE;i++){
		t=board[row][i];
		auxilaryArray[t]=1;
	}
	if(auxilaryArrayIsFull(auxilaryArray)) return 1;
	return 0;
}
int columnIsCorrect(int board[SIZE][SIZE], int column){
	int auxilaryArray[SIZE];
	initializeAuxilaryArray(auxilaryArray);
	int i,t;

	for(i=0;i<=SIZE;i++){
		t=board[i][column];
		auxilaryArray[t]=1;
	}
	if(auxilaryArrayIsFull(auxilaryArray)) return 1;
	return 0;
}
void printBoard(int board[SIZE][SIZE]){
    int i,j;
    printf("  |123456789\n");
    printf("--+---------\n");
    for(i=0;i<SIZE;i++){
        printf("%d | ",i+1);
        for(j=0;j<SIZE;j++){
            if(board[i][j]==0) printf(" ");
            else printf("%d",board[i][j]);
        }
        printf("\n");
    }
}

void doAuxilarySteps(int board[SIZE][SIZE]){
	
}

int solve(int board[SIZE][SIZE]){

	if(isCorrect(board)){
		printBoard(board);
		return 1;
	}
	
	if(boardIsFull(board)) return 0;
/*
	doAuxilarySteps(board);

	int foundEmptyCell=0;
	int i,j=-1;

	while((!foundEmptyCell)&&(j<SIZE)){
		j++;
		for(i=0;i<SIZE;i++){
			if(board[i][j]==0){
				foundEmptyCell=1;
				exit;
			}
		}
	}

	int t;
	for(t=1;t<=SIZE;t++){
		board[i][j]=t;
		solve(board);
	}	
*/
}

int isCorrect(int board[SIZE][SIZE]){
	int i,j;
	for(i=0;i<SIZE;i++){
		if(!(rowIsCorrect(board,i))) return 0;
		if(!(columnIsCorrect(board,i))) return 0;
	}
	for(i=0;i<SIZE;i+SQRTS){
		for(j=0;j<SIZE;j+SQRTS){
			if(!(cubeIsCorrect,board,i,j)) return 0;
		}
	}
	return 1;
}

void checkSystem(){
                            //0 1 2 3 4 5 6 7 8
    int example[SIZE][SIZE]={{1,2,6,4,3,7,8,9,5}, /*0*/
                             {0,0,0,0,0,5,0,0,0}, /*1*/
                             {0,0,0,0,0,6,0,0,0}, /*2*/
                             {0,0,0,0,0,8,0,0,0}, /*3*/
                             {0,0,0,0,0,9,0,0,0}, /*4*/
                             {0,0,0,0,0,2,0,0,0}, /*5*/
                             {0,0,0,2,5,3,0,0,0}, /*6*/
                             {0,0,0,7,6,4,0,0,0}, /*7*/
                             {0,0,0,9,8,1,0,0,0}};/*8*/


    printf("Printing example board...    \n\n");
    printBoard(example);

    solve(example);
}

int main(){
	checkSystem();
	return 0;
}

